package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 平衡二叉树
 * <p>
 * 平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。
 * @date 2025/4/14 19:18
 */
public class IsBalanced_110 {


    /**
     * 参考dmsxl：dfs-后序
     * 同官解-自底向上的递归
     * <p>
     * 思路：
     * 统计左右子树的高度，及高度差；若为-1，表示该节点的子树中有 非平衡二叉树
     */
    public boolean isBalanced2(TreeNode root) {
        return getHeight2(root) == -1 ? false : true;
    }

    public int getHeight2(TreeNode node) {
        if (node == null) return 0;

        // 左、右子树任一高度为 -1，表明子树中有非平衡二叉树
        // 左
        int leftHeight = getHeight2(node.left);
        if (leftHeight == -1) return -1;
        // 右
        int rightHeight = getHeight2(node.right);
        if (rightHeight == -1) return -1;

        // 中
        int result;
        if (Math.abs(leftHeight - rightHeight) > 1) {
            // 非平衡二叉树
            result = -1;
        } else {
            // 平衡二叉树，则记录当前节点的深度
            result = Math.max(leftHeight, rightHeight) + 1;
        }

        return result;
    }

    /**
     * 个解：dfs-后序
     * 同官解-自顶向下
     * <p>
     * 分析：
     * 该题定义的平衡二叉树，只是左右子树高度差不超过1，并没有要求节点值，所以不是我们常规说的AVL。
     * 递归判断每个节点的左右子树是否为题目所说的平衡二叉树。
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        // 以当前节点为根的树左右子树高度差 > 1，则该节点不是题目所说的 平衡二叉树
        if (leftHeight - rightHeight > 1 || leftHeight - rightHeight < -1) {
            return false;
        }

        // 左
        boolean leftBalance = isBalanced(root.left);
        // 右
        boolean rightBalance = isBalanced(root.right);

        // 中
        return leftBalance && rightBalance;
    }

    public int getHeight(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);

        return Math.max(leftHeight, rightHeight) + 1;
    }

}
